package com.hanxiaozhang.no10leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给定一个数组和一个目标值，在数组中找出所有合为目标值的组合。数组中的每个元素只能用一次
 * 注意：所有数字都是正整数且结果中不包含重复组合
 * 示例1:
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8
 * 输出: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
 * 示例2:
 * 输入: candidates = [2,5,2,1,2], target = 5
 * 输出: [ [1,2,2], [5] ]
 *
 * 思路：
 * 1. 在No39CombinationSum基础上，每次回溯从下一个位置开始
 * 2. 循环位置大于开始位置时，判断arr[i] 与  arr[i - 1] 是否相等，相等 继续下次循环 -> 目的去重 todo 疑问 2024-01-18
 *
 * @author hanxinghua
 * @create 2024/1/12
 * @since 1.0.0
 */
public class No40CombinationSumII {


    public static void main(String[] args) {

        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        List<List<Integer>> lists = combinationSum(candidates, target);
        System.out.println(lists);

    }

    public static List<List<Integer>> combinationSum(int[] arr, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(arr);
        backTrack(0, arr, new ArrayList<>(), result, target, 0);
        return result;
    }


    private static int backTrack(int sum, int[] arr, List<Integer> curList, List<List<Integer>> result, int target, int start) {

        if (sum > target) {
            return 0;
        }
        if (sum == target) {
            result.add(new ArrayList<>(curList));
            return 1;
        } else {
            for (int i = start; i < arr.length; i++) {

                // for example {10, 1, 2, 7, 6, 1, 5}
                // you got double 1, so if you don't check this, you will get double result start with 1
                // 循环位置大于开始位置时，判断arr[i] 与  arr[i - 1] 是否相等，相等 继续下次循环
                if (i > start && arr[i] == arr[i - 1]) {
                    continue;
                }

                curList.add(arr[i]);
                int sumResult = backTrack(sum + arr[i], arr, curList, result, target, i + 1);
                curList.remove(curList.size() - 1);
                if (sumResult != -1) {
                    break;
                }
            }
        }
        return -1;
    }


}
